// David Doering
// CSCE 411 - Homework 10++
// email: imdave@neo.tamu.edu

import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.PrintStream;

public class Sudoku {
	// Global size of the matrix row and column
	static int n = 0;
	static int index = 0;
	
	// Store all possible values within the Sudoku puzzle
	static char[] values = null;
	static char[] backupValues = new char[9];

	// Used in determining the total running time of the program
	static float startTime = 0;
	static float endTime = 0;
	static float totalTime = 0;
	
	static boolean switchCompute = false;
	
	// Takes the input and puts it in an array of arrays of characters
	@SuppressWarnings("deprecation")
	static char[][] parse() throws FileNotFoundException{
		// Count to run through each row and column
		// Size to ensure the matrix is properly created
		int count = 0;
		int size = 0;
		String s = null;
		boolean addValue = true;
		
		// Problem stores the initial state of the matrix
		// charArray stores the current array which will be put in the matrix
		char[][] problem = null;
		char[] charArray = null;
		
		FileInputStream inData = new FileInputStream("input.txt");
		try {
			s = new DataInputStream(inData).readLine();
			size = s.length();
			n = size;
			problem = new char[size][size];
			charArray = new char[size];
			values = new char[size];
			
			charArray = s.toCharArray();
			
			// Traverse the first line of input, putting necessary values in the
			// matrix as well as in the possible values array
			for(int j = 0; j < size; j++){
				char c = charArray[j];
				problem[count][j] = c;
				if(c != '.'){
					for(int z = 0; z < size; z++){
						if(c == values[z]){
							addValue = false;
						}
					}
					if(addValue){
						values[index] = c;
						index++;
					}
				}
			}
			// Move to the next row of the matrix
			count++;
			
			// Takes the size of the first string and runs
			// through that number of times to create the
			// proper matrix
			while(count < size){
				if ((s = new DataInputStream(inData).readLine()) != null && s.length() == size) {
					charArray = s.toCharArray();
						
					for(int j = 0; j < s.length(); j++){
						char c = charArray[j];
						problem[count][j] = c;
						addValue = true;
						if(c != '.'){
							for(int z = 0; z < size; z++){
								if(c == values[z]){
									addValue = false;
								}
							}
							if(addValue){
								values[index] = c;
								index++;
							}
						}
					}
					
					count++;
				}
				else
					System.out.println("Improper input size: Try again.");
			}
		} 
		
		catch (IOException e) {
			e.printStackTrace();
		}

		return problem;
	}
	
	// If a puzzle is given that does not have all the values
	// possible: Example
	//				123.
	//				3..1
	// 				23..
	//				...2
	// A person could assume the missing value is 4, but since
	// the value is not given in the problem, there is no concrete
	// value to the 4th variable, so I assign it a filler value
	static void checkValues(char allValues[]){
		backupValues[0] = '&';
		backupValues[1] = '%';
		backupValues[2] = '*';
		backupValues[3] = '$';
		backupValues[4] = '#';
		backupValues[5] = '@';
		backupValues[6] = ')';
		backupValues[7] = '(';
		backupValues[8] = '!';
		
		for(int i = index; i < n; i++){
			for(int x = 0; x < 8; x++)
				if(allValues[i] != backupValues[x]){
					allValues[i] = backupValues[x];
					x = 8;
			}
		}
	}
	
	// Used to find the most filled column to start with
	static int rowSize = 0;
	static boolean rowCheck = true;
	
	// If the first row has more predetermined values than the last
	// row, rowCheck stays true, otherwise it is changed to false.
	// This determines which direction the algorithm will progress.
	static void checkSize(char grid[][]){
		int tempSize = 0;
		for(int x = 0; x < n; x++){
			if(grid[x][0] == '.'){
				tempSize--;
			}
		}
		rowSize = tempSize;
		tempSize = n;
		
		for(int x = 0; x < n; x++){
			if(grid[x][n-1] == '.'){
				tempSize--;
			}
		}
		
		if(rowSize < tempSize){
			rowCheck = false;
		}
	}
	
	// Check if a given value is valid at each spot in the puzzle
	static boolean valid(int i, int j, char val, char[][] matrix) {
        
		// Check the rows of the Sudoku puzzle if the value is already there
		for (int x = 0; x < n; ++x)
            if (val == matrix[x][j])
                return false;

		// Check the columns of the Sudoku puzzle if the value is already there
        for (int y = 0; y < n; ++y)
            if (val == matrix[i][y])
                return false;

        // Check the "Squares" of the puzzle if necessary.
        // If the Sudoku puzzle has a whole number square root,
        // then there are boxes inside the puzzle, and you must
        // also check those boxes, otherwise it is just a Latin square.
        if(Math.sqrt(n)%1 == 0){
        	// Offsets are 0 if you are in the first square, otherwise
        	// they increase by the square root of the row/column sizes
        	// when you move to the next square
	        int rowOffset =  (i / (int)Math.sqrt(n)) * (int)Math.sqrt(n);
	        int colOffset =  (j / (int)Math.sqrt(n)) * (int)Math.sqrt(n);
	        
	        // Traverse through each individual square

	        for (int k = 0; k < Math.sqrt(n); k++)
	            for (int m = 0; m < Math.sqrt(n); m++)
	                if (val == matrix[rowOffset+k][colOffset+m])
	                    return false;
        }
        
        return true; 
    }


	// Solve the puzzle using the previous value verification
	// process. All possible values are stored and compared
	// with the current state of the puzzle.
	static boolean compute(int i, int j, char[][] matrix) {
        // Before it computes, if finds if the top row or
		// the bottom row has more completed values in the
		// given grid, and starts at the row with the most
		// values already filled in.
		
		// Reset i when you reach the end of a row
    	// Increment/Decrement j when i is at the end of the row
    	// Matrix values go from [0] to [n-1], so return if 
		// j is greater or less than this and the solution is complete
		
		if (i == n) {
            i = 0;
            //if(rowCheck){
            	if(!switchCompute){
                    if(++j == n){
                    	switchCompute = true;
                    	return true;
                    }
            	}
            	else if(switchCompute)
            		if(--j == -1)
            			return true;
            //}
          //  else if(--j == -1)
          //          return true;
            
        }
  
        // Do not visit values that are already set, just move to the next cell
        if (matrix[i][j] != '.')
            return compute(i+1,j,matrix);
        
        // Recursively traverse the matrix checking which value is valid, 
        // visits a deeper node then traverses back to the source when it
        // completes. Hence DFS.
        for (int val = 0; val < n; ++val){
        	char c = values[val];
        	if (valid(i,j,c,matrix)) {
                matrix[i][j] = c;
                if (compute(i+1,j,matrix))
                    return true;
        	}
        }

        matrix[i][j] = '.';
        return false;
    }


	static void combine(char[][] sol1, char[][] sol2){
		for(int x = 0; x < n; x++){
			for(int y = 0; y < n; y++){
				if(sol1[x][y] == '.'){
					sol1[x][y] = sol2[x][y];
				}
			}
		}
	}
	// Print the solved puzzle if it exists.
	static void printSolution(char[][] solution){
		int sqrt = (int)Math.sqrt(n);
		
		// Start the box display then show everything else properly
		for(int i = 0; i < n; i++){
				if((i)%sqrt == 0){
					System.out.print('\n');
					for(int z = 0; z < n+sqrt+1; z++)
						System.out.print('-');
					System.out.print('\n');
				}
				else System.out.print('\n');
				System.out.print('|');
			for(int j = 0; j < n; j++){
				System.out.print(solution[i][j]);
				if((j+1)%sqrt == 0)
					System.out.print('|');
			}
		}
		
		// Finish the box
		System.out.print('\n');
		for(int z = 0; z < n+sqrt+1; z++)
			System.out.print('-');
		System.out.print('\n');
	}
	
	// Output stream is used to write the timing information
	// to an external file, it does not overwrite the information
	// every time it is called, to allow for multiple times.
	static void writeToFile(float time){
		FileOutputStream fout;		

		try
		{
		 
		    fout = new FileOutputStream ("time.txt", true);

		    new PrintStream(fout).println (time);
		    fout.close();		
		}
		
		catch (IOException e)
		{
			System.err.println ("Unable to write to file");
			System.exit(-1);
		}
	}
	
	public static void main(String[] args) throws IOException{

	//	for(int i = 0; i < 10; i++)
	//	{
			n = 0;
			index = 0;
			startTime = System.currentTimeMillis();
			
			// This creates the initial matrix which holds the values
			// of all the predetermined characters
			char[][] sudokuProblem = parse();
			
			char[][] sudokuStart = new char[n][n];
			for(int x = 0; x < n; x++){
				for(int y = 0; y < n; y++){
					sudokuStart[x][y] = sudokuProblem[x][y];
				}
			} 
			char[][] sudoku1 = new char[n][n];
			char[][] sudoku2 = new char[n][n];
			
			boolean solve1 = false;
			boolean solve2 = false;
			System.out.println("Parse complete.");
			// Check if all possible values are given in the problem, if
			// not, use filler values
			checkValues(values);
			System.out.println("Validity complete.");
			
			// Check if the top row or the bottom row has more values
			// already determined, start there
			checkSize(sudokuProblem);
			System.out.println("Check complete.");
			// This runs if the first row has more values,
			// algorithm works downward

			if(compute(0,n/2,sudokuProblem))
				solve1 = true;
			sudoku1 = sudokuProblem;

			if (compute(0,n/2,sudokuStart))
				solve2 = true;
			sudoku2 = sudokuStart;
			
			if(solve1 && solve2){
				combine(sudoku1, sudoku2);
				compute(0,0,sudoku1);
				printSolution(sudoku1);
			}
			
			else
				System.out.println("No solution exists.");
			
			System.out.println("Program complete.");
			
			endTime = System.currentTimeMillis();
			
			totalTime = endTime - startTime;
			
			writeToFile(totalTime);
	//	}

	}	
}
